package Tree;

import java.util.*;

public class leet_103 {
    public static void main(String[] args) {

    }
}

class Solution_103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = BFS(root);
        return result;
    }

    public List<List<Integer>> BFS(TreeNode root){
        List<List<Integer>> result = new ArrayList<>();
        if(root==null){return result;}
        // 入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 设置是否进行顺序转换的一个控制
        boolean isShift = false;
        // 如果队列不为空就继续走
        while(!queue.isEmpty()){
            // 当前层级的结点数量
            int size = queue.size();
            List<Integer> tmpList = new ArrayList<>();
            for(int i=0; i<size; i++){
                // 队列抛出结点信息
                TreeNode tmpNode = queue.poll();
                tmpList.add(tmpNode.val);
                if(tmpNode.left!=null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right!=null){
                    queue.offer(tmpNode.right);
                }
            }
            if(isShift){
                // 翻转该List
                Collections.reverse(tmpList);
                isShift = false;
            }else {
                isShift = true;
            }
            result.add(tmpList);
        }
        return result;
    }

}

